#include "BTreeNode.h"
#include <iostream>
using namespace std;

/*
 LeafNode
 insert (need to check if node is full)
 NonLeafNode
 ~read
 write
 getKeyCount
 insert
 insertAndSplit
 locateChildPtr
 initializeRoot
 */


//
// helper functions for page manipultation
//

// compute the pointer to the n'th slot in a page
static char* slotPtrL(char* page, int n);

// read the record in the n'th slot in the page
static void readSlotL(const char* page, int n, int& key, RecordId& value);

//write the sibling pid right after the count slot
static void writeSibling(char*page, PageId pid);

// write the record to the n'th slot in the page
static void writeSlotL(char* page, int n, int key, RecordId value);

// get # records stored in the page
static int getRecordCountL(const char* page);

// update # records stored in the page
static void setRecordCountL(char* page, int count);






// compute the pointer to the n'th slot in a page
static char* slotPtrNL(char* page, int n);

// read the record in the n'th slot in the page
static void readSlotNL(const char* page, int n, int& key, PageId& value);

//write the less than pid right after the count slot
static void writeLessThan(char*page, PageId pid);

// write the record to the n'th slot in the page
static void writeSlotNL(char* page, int n, int key, PageId pid);

// get # records stored in the page
static int getRecordCountNL(const char* page);

// update # records stored in the page
static void setRecordCountNL(char* page, int count);




BTLeafNode::BTLeafNode(){
    siblingPid = -1;
    memset(buffer, 0, PageFile::PAGE_SIZE);
    buffer[PageFile::PAGE_SIZE] = '\0';
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{ 
    
    RC rc = 0;
    int tempKey = -1;
	RecordId tempRid;
    tempRid.pid = -1;
    tempRid.sid = -1;
    
    memset(buffer, 0, PageFile::PAGE_SIZE);
    leafNode.couple.clear();
    if((rc = pf.read(pid, buffer)) < 0) return rc;
    
    for (int i = 0; i < getRecordCountL(buffer); i++) {
        readSlotL(buffer, i, tempKey, tempRid);
        if((rc = insert(tempKey, tempRid)) < 0) return rc;
    }
    //read the sibling
    memcpy(&siblingPid, buffer + sizeof(int), sizeof(PageId));
	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{ 
    
	//CHECK format of buffer
	//place all keys and PageIds into the buffer
	
    memset(buffer, 0, PageFile::PAGE_SIZE);
    map<int, RecordId>::iterator iter = leafNode.couple.begin();
    for (int i = 0; iter != leafNode.couple.end(); i++, iter++) {
        writeSlotL(buffer, i, iter->first, iter->second);
    }
    writeSibling(buffer, siblingPid);
    setRecordCountL(buffer, getKeyCount());
    
    return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{ 
	return leafNode.couple.size(); 
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{ 
	map<int, RecordId>::iterator iter = leafNode.couple.find(key);
    if (getKeyCount() > 83) {
        return RC_NODE_FULL;
    }
    //I don't know if this is supposed to be checked
    //I also don't know if key can be negative
//    else if (rid.pid < 0 || rid.sid < 0){
//        return RC_INVALID_RID;
//    }
	else if (iter != leafNode.couple.end()) {
		return RC_INVALID_ATTRIBUTE;
	}
    else {
        leafNode.couple[key]=rid;
    }
	return 0;  
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{ 
    RC rc = 0;
    RecordId tempRid;
    
    map<int, RecordId>::iterator iter0 = leafNode.couple.find(key);
    if (sibling.getKeyCount() != 0) {
        return RC_INVALID_ATTRIBUTE;
    }
    else if (iter0 != leafNode.couple.end()) {
        return RC_INVALID_ATTRIBUTE;
    }
    else {
//        rc = insert(key, rid);
//        //check for insert errors
//        if (rc != 0) {return rc;}
       
        leafNode.couple[key]=rid;
        
        int splitNum = (getKeyCount()+1)/2;
//        cout << "split num : " << splitNum << endl;
        map<int, RecordId>::iterator iter = leafNode.couple.begin(), 
                                  iterMid = leafNode.couple.begin(), 
                                  iterEnd = leafNode.couple.end();
        //iterate though the map until the mid value
        //at the mid couple, record the iterator,
        //function should keep at least half and give away at most half
        for (int i = 0; iter != iterEnd; i++, iter++) {
            if (i < splitNum) {continue;}
            else{
                if (i == splitNum) {
                    //check for insert errors
                    rc = sibling.insert(iter->first, iter->second);
                    if(rc  != 0) {return rc;}
                    
                    iterMid = iter;
                    siblingKey = iter->first;
                }
                else {
                    //check for insert errors
                    rc = sibling.insert(iter->first, iter->second);
                    if(rc  != 0) {return rc;}
                }
            }
            sibling.readEntry(0, siblingKey, tempRid);
        }
        leafNode.couple.erase(iterMid, iterEnd);
           
    }
    return 0; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 
    map<int, RecordId>::iterator iter = leafNode.couple.begin();
    for (int i = 0; iter != leafNode.couple.end(); i++, iter++) {
        if (iter->first >= searchKey) {
            eid = i;
            return 0;
        }
    }
    return RC_NO_SUCH_RECORD; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
    //should I set key, and rid to -1 if failed?
    
    //I'm assuming eid index begins at 0
    if (eid < 0) {
        return RC_NO_SUCH_RECORD;
    }
    else if (eid >= getKeyCount()){
        //requesting an eid that is greater than number of keys
        return RC_NO_SUCH_RECORD;
    }
    else{
        map<int, RecordId>::iterator iter = leafNode.couple.begin();
        for (int i = 0; iter != leafNode.couple.end(); i++, iter++) {
            if (i < eid) {
                continue;
            }
            else if (i == eid)
            {
                key = iter->first;
                rid = iter->second;
                return 0;
                break;
            }
            else 
            {
                cout << "Reached else in readEntry, aw it shouldn't have!" << endl;
            }
        }
    }
     
    return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
    return siblingPid; 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
    if (pid < 0) {
        return RC_INVALID_PID;
    }
    siblingPid = pid;
    return 0; 
}

void BTLeafNode::showContents()
{
    cout << "siblingPid: " << siblingPid << endl;
    map<int, RecordId>::iterator iter = leafNode.couple.begin();
    for (int i = 0; iter != leafNode.couple.end(); i++, iter++) {
        cout    << "key: " << iter->first 
        << ", pid: " << iter->second.pid
        << ", sid: " << iter->second.sid
        << endl;
    }
}












BTNonLeafNode::BTNonLeafNode(){
    memset(buffer, 0, PageFile::PAGE_SIZE);
    buffer[PageFile::PAGE_SIZE] = '\0';
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{ 
    RC rc = 0;
    int tempKey = -1;
	PageId tempPid = -1;
    
    nonLeafNode.couple.clear();
    if((rc = pf.read(pid, buffer)) < 0) return rc;
    
    for (int i = 0; i < getRecordCountNL(buffer); i++) {
        readSlotNL(buffer, i, tempKey, tempPid);
        if((rc = insert(tempKey, tempPid)) < 0) return rc;
    }
    memcpy(&lessThanPid, buffer + sizeof(int), sizeof(PageId));

	return 0; 
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{ 
    memset(buffer, 0, PageFile::PAGE_SIZE);
    map<int, PageId>::iterator iter = nonLeafNode.couple.begin();
    for (int i = 0; iter != nonLeafNode.couple.end(); i++, iter++) {
        writeSlotNL(buffer, i, iter->first, iter->second);
    }
    setRecordCountNL(buffer, getKeyCount());
    writeLessThan(buffer, lessThanPid);

    return pf.write(pid, buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{ 
	//ADJUST SIZE because of first -1;
	return nonLeafNode.couple.size(); 
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 
    map<int, PageId>::iterator iter = nonLeafNode.couple.find(key);

    if (getKeyCount() > 126) {
        return RC_NODE_FULL;
    }
    else if (iter != nonLeafNode.couple.end()) {
        return RC_INVALID_ATTRIBUTE;
    }
	nonLeafNode.couple[key]=pid;
	return 0; 
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
    RC rc = 0;
    map<int, PageId>::iterator iter0 = nonLeafNode.couple.find(key);
	if (sibling.getKeyCount() > 0) {
		return RC_INVALID_ATTRIBUTE;
	}
    else if (iter0 != nonLeafNode.couple.end()) {
        return RC_INVALID_ATTRIBUTE;
    }
    //check insert for errors
//	rc = insert(key, pid);
//    if (rc != 0) {return rc;}
    nonLeafNode.couple[key]=pid;
        
	int splitNum = getKeyCount()/2;
	
	
	map<int, PageId>::iterator iter = nonLeafNode.couple.begin(), 
							iterMid = nonLeafNode.couple.begin(), 
							iterEnd = nonLeafNode.couple.end();
	
	
	//iterate though the map until the mid value
	//at the mid couple, record the iterator, initialize NEW sibling
	
	for (int i = 0; iter != iterEnd; i++, iter++) {
		// <= because of the extra lessthan couple
		// I designed the couple struct so the pid points to values >= key
		// every node will need one of these padded couples so there's a <
		if ( i < splitNum ) {continue;}
		
		else {
			//==, again < because of the extra lessthan couple
			if(i == splitNum)
			{
				//initialize key so lessthan pid has nonkey value.
				iterMid = iter;
				midKey = iter->first;
                sibling.setLessThan(iter->second);
			}
			else{
                rc = sibling.insert(iter->first, iter->second);
                if (rc != 0){return rc;}
            }    
		}
	}
	nonLeafNode.couple.erase(iterMid, iterEnd);
	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{ 
	
	map<int, PageId>::iterator iter1 = nonLeafNode.couple.begin(),
                               iter0;
    iter0 = iter1;
    iter1++;
    if (searchKey < iter0->first) {
        pid = lessThanPid;
        return 0;
    }
    for (; iter0 != nonLeafNode.couple.end(); iter0++, iter1++) {
        if(iter0->first == searchKey)
        {
            pid = iter0->second;
            return 0;
        }
        else if (iter1 == nonLeafNode.couple.end()){
            pid = iter0->second;
            return 0;
        }
        else if (iter0->first < searchKey && iter1->first > searchKey){
            pid = iter0->second;
            return 0;
        }
        else continue;
    }
    return -1;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{ 
	setLessThan(pid1);
	nonLeafNode.couple[key] = pid2;
	nonLeafNode.pidLess = pid1;
	return 0; 
}

void BTNonLeafNode::showContents()
{
    cout << "<pid " << lessThanPid << endl;
    map<int, PageId>::iterator iter = nonLeafNode.couple.begin();
   
    for (int i = 0; iter != nonLeafNode.couple.end(); i++, iter++) {
        
        cout    << "key: " << iter->first 
                << ", pid: " << iter->second
                << endl;
    }
    
}


RC BTNonLeafNode::setLessThan(const PageId& pid)
{
    lessThanPid = pid;
    return 0;
}








static int getRecordCountL(const char* page)
{
    int count;
    
    // the first four bytes of a page contains # records in the page
    memcpy(&count, page, sizeof(int));
    return count;
}

static void setRecordCountL(char* page, int count)
{
    // the first four bytes of a page contains # records in the page
    memcpy(page, &count, sizeof(int));
}

static char* slotPtrL(char* page, int n) 
{
    // compute the location of the n'th slot in a page.
    // remember that the first four bytes in a page is used to store
    //**and the second 4 bytes are for the sibling pointer;
    // # records in the page and each slot consists of an integer and
    // a string of length MAX_VALUE_LENGTH
    return (page+sizeof(int) + sizeof(PageId)) + (sizeof(int)+sizeof(PageId) + sizeof(int))*n;
}

static void readSlotL(const char* page, int n, int& key, RecordId& rid)
{
    // compute the location of the record
    char *ptr = slotPtrL(const_cast<char*>(page), n);
    
    // read the key 
    memcpy(&key, ptr, sizeof(int));
    
    // read the pid
    memcpy(&rid.pid, ptr + sizeof(int), sizeof(PageId));
    
    // read the sid
    memcpy(&rid.sid, ptr + sizeof(int)+ sizeof(PageId), sizeof(int));
}

static void writeSibling(char*page, PageId pid)
{
    char *ptr =  page + sizeof(int);
    
    //store the sibling pid
    memcpy(ptr, &pid, sizeof(PageId));
}

static void writeSlotL(char* page, int n, int key, RecordId rid)
{
    // compute the location of the record
    char *ptr = slotPtrL(page, n);
    
    // store the key
    memcpy(ptr, &key, sizeof(int));
    
    // store the rid.pid 
    memcpy(ptr + sizeof(int), &rid.pid, sizeof(PageId));
    
    // store the rid.sid
    memcpy(ptr + sizeof(int) + sizeof(PageId),&rid.sid, sizeof(int));
    
}







static int getRecordCountNL(const char* page)
{
    int count;
    
    // the first four bytes of a page contains # records in the page
    memcpy(&count, page, sizeof(int));
    return count;
}

static void setRecordCountNL(char* page, int count)
{
    // the first four bytes of a page contains # records in the page
    memcpy(page, &count, sizeof(int));
}

static char* slotPtrNL(char* page, int n) 
{
    // compute the location of the n'th slot in a page.
    // remember that the first four bytes in a page is used to store
    // # records in the page and each slot consists of an integer and
    // a string of length MAX_VALUE_LENGTH
    return (page+sizeof(int)+ sizeof(PageId)) + (sizeof(int)+sizeof(PageId))*n;
}

static void readSlotNL(const char* page, int n, int& key, PageId& pid)
{
    // compute the location of the record
    char *ptr = slotPtrNL(const_cast<char*>(page), n);
    
    // read the key 
    memcpy(&key, ptr, sizeof(int));
    
    // read the value
    memcpy(&pid, ptr + sizeof(int), sizeof(PageId));
}

static void writeLessThan(char*page, PageId pid)
{
    char *ptr =  page + sizeof(int);
    
    //store the sibling pid
    memcpy(ptr, &pid, sizeof(PageId));
}

static void writeSlotNL(char* page, int n, int key, PageId pid)
{
    // compute the location of the record
    char *ptr = slotPtrNL(page, n);
    
    // store the key
    memcpy(ptr, &key, sizeof(int));
    
    // store the pid. 
 
    memcpy(ptr + sizeof(int), &pid, sizeof(PageId));

}


